package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-27 10:32
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 括号生成 {
    public Map<Integer, List<String>> store = new HashMap<>();

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (store.containsKey(n)){
            return store.get(n);
        }
        if (n == 0)   {
            List<String> list = new ArrayList<>();
            list.add("");
            return list;
        }
        for (int i = 1; i <= n; i++) {
            List<String> A = generateParenthesis(i-1);
            List<String> B = generateParenthesis(n-i);

            for (String s : A) {
                for (String s1 : B) {
                    ans.add("(" + s +")" + s1);
                }
            }
        }
        store.put(n,ans);
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new 括号生成().generateParenthesis(3));
    }
}
